package com.javaDemo.ti;

import java.util.*;

/**
 * 单调栈算法题目详解
 * 
 * @author csy
 * @description 面试中常见的单调栈算法题的详细解析
 */
public class MonotonicStackExamples {

    /**
     * 【题目1】下一个更大元素
     * 
     * 问题描述：
     * 给定一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存储-1。
     * 
     * 解题思路详解：
     * 1. 为什么用单调栈？
     * - 单调栈可以在O(n)时间内找到每个元素的下一个更大元素
     * - 栈内元素保持单调递减，便于快速找到下一个更大元素
     * 
     * 2. 详细步骤解析：
     * a) 初始化：
     * - 创建一个单调递减栈
     * - 创建结果数组，初始化为-1
     * 
     * b) 遍历数组：
     * - 当前元素大于栈顶元素时，栈顶元素找到了下一个更大元素
     * - 更新结果数组，弹出栈顶元素
     * - 重复此过程直到栈为空或当前元素小于栈顶元素
     * 
     * 3. 举例说明：
     * 输入：[2,1,2,4,3]
     * 过程：
     * - 2入栈
     * - 1入栈
     * - 2>1，1的下一个更大元素是2
     * - 4>2，2的下一个更大元素是4
     * - 3入栈
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static int[] nextGreaterElement(int[] nums) {
        // 创建结果数组，初始化所有元素为-1（表示没有找到更大的元素）
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        // 创建单调递减栈，存储元素的索引
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums.length; i++) {
            // 当栈不为空且当前元素大于栈顶元素时，说明找到了栈顶元素的下一个更大元素
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                // 弹出栈顶元素的索引，并将当前元素设置为其下一个更大元素
                result[stack.pop()] = nums[i];
            }
            // 将当前元素的索引入栈
            stack.push(i);
        }

        return result;
    }

    /**
     * 【题目2】每日温度
     * 
     * 问题描述：
     * 给定一个数组，返回一个等长的数组，对应索引存储着下一个更高温度出现在几天后。
     * 
     * 解题思路详解：
     * 1. 为什么用单调栈？
     * - 需要找到下一个更大的元素及其距离
     * - 单调栈可以存储元素的索引，方便计算天数差
     * 
     * 2. 详细步骤解析：
     * a) 初始化：
     * - 创建单调递减栈（存储索引）
     * - 创建结果数组，初始化为0
     * 
     * b) 遍历数组：
     * - 当前温度大于栈顶索引对应的温度
     * - 计算天数差并更新结果数组
     * - 当前索引入栈
     * 
     * 3. 举例说明：
     * 输入：[73,74,75,71,69,72,76,73]
     * 过程：
     * - 73入栈
     * - 74>73，73等待1天
     * - 75>74，74等待1天
     * - 71入栈
     * ...
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static int[] dailyTemperatures(int[] temperatures) {
        // 创建结果数组，默认值为0（表示没有找到更高的温度）
        int[] result = new int[temperatures.length];
        // 创建单调递减栈，存储温度的索引
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < temperatures.length; i++) {
            // 当栈不为空且当前温度高于栈顶索引对应的温度时
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                // 计算等待天数：当前天数减去栈顶元素的天数
                int prevDay = stack.pop();
                result[prevDay] = i - prevDay;
            }
            // 将当前温度的索引入栈
            stack.push(i);
        }

        return result;
    }

    /**
     * 【题目3】柱状图中最大的矩形
     * 
     * 问题描述：
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * 
     * 解题思路详解：
     * 1. 为什么用单调栈？
     * - 需要找到每个柱子左右两边第一个小于它的柱子
     * - 单调递增栈可以帮助我们找到这些边界
     * 
     * 2. 详细步骤解析：
     * a) 初始化：
     * - 创建单调递增栈
     * - 添加哨兵元素处理边界情况
     * 
     * b) 遍历数组：
     * - 当前高度小于栈顶柱子高度
     * - 计算栈顶柱子能够形成的最大矩形面积
     * - 更新最大面积
     * 
     * 3. 举例说明：
     * 输入：[2,1,5,6,2,3]
     * 过程：
     * - 添加哨兵0
     * - 2入栈
     * - 1<2，计算2的面积
     * - 5,6入栈
     * - 2<6，计算6和5的面积
     * ...
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static int largestRectangleArea(int[] heights) {
        // 记录最大矩形面积
        int maxArea = 0;
        // 创建单调递增栈，存储柱子的索引
        Stack<Integer> stack = new Stack<>();
        // 在数组两端添加高度为0的柱子，处理边界情况
        int[] newHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeights, 1, heights.length);

        for (int i = 0; i < newHeights.length; i++) {
            // 当栈不为空且当前柱子高度小于栈顶柱子高度时，计算栈顶柱子能形成的最大矩形
            while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                // 弹出栈顶柱子，计算以该柱子高度为高的矩形面积
                int height = newHeights[stack.pop()];
                // 宽度为当前位置到新栈顶位置的距离减1
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            // 将当前柱子的索引入栈
            stack.push(i);
        }

        return maxArea;
    }

    /**
     * 【题目4】接雨水
     * 
     * 问题描述：
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 
     * 解题思路详解：
     * 1. 为什么用单调栈？
     * - 需要找到每个位置能接的雨水量
     * - 单调递减栈可以帮助我们找到凹槽
     * 
     * 2. 详细步骤解析：
     * a) 初始化：
     * - 创建单调递减栈
     * - 记录总雨水量
     * 
     * b) 遍历数组：
     * - 当前高度大于栈顶元素时形成凹槽
     * - 计算凹槽能接的雨水量
     * - 累加到总雨水量
     * 
     * 3. 举例说明：
     * 输入：[0,1,0,2,1,0,1,3,2,1,2,1]
     * 过程：
     * - 0,1入栈
     * - 0形成凹槽
     * - 2形成更大的凹槽
     * ...
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static int trap(int[] height) {
        // 记录总雨水量
        int totalWater = 0;
        // 创建单调递减栈，存储柱子的索引
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < height.length; i++) {
            // 当栈不为空且当前柱子高度大于栈顶柱子高度时，形成凹槽可以接雨水
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 凹槽的底部（弹出栈顶元素）
                int bottom = stack.pop();
                if (stack.isEmpty())
                    break;
                // 计算凹槽的宽度
                int distance = i - stack.peek() - 1;
                // 计算凹槽的高度（取左右两边较矮的高度减去底部高度）
                int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[bottom];
                // 累加当前凹槽能接的雨水量
                totalWater += distance * boundedHeight;
            }
            // 将当前柱子的索引入栈
            stack.push(i);
        }

        return totalWater;
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试下一个更大元素
        System.out.println("=== 下一个更大元素测试 ===");
        int[] nums1 = { 2, 1, 2, 4, 3 };
        int[] result1 = nextGreaterElement(nums1);
        System.out.println("输入数组：" + Arrays.toString(nums1));
        System.out.println("结果：" + Arrays.toString(result1) + "\n");

        // 测试每日温度
        System.out.println("=== 每日温度测试 ===");
        int[] temperatures = { 73, 74, 75, 71, 69, 72, 76, 73 };
        int[] result2 = dailyTemperatures(temperatures);
        System.out.println("输入温度：" + Arrays.toString(temperatures));
        System.out.println("等待天数：" + Arrays.toString(result2) + "\n");

        // 测试柱状图中最大的矩形
        System.out.println("=== 柱状图最大矩形测试 ===");
        int[] heights = { 2, 1, 5, 6, 2, 3 };
        int result3 = largestRectangleArea(heights);
        System.out.println("输入高度：" + Arrays.toString(heights));
        System.out.println("最大面积：" + result3 + "\n");

        // 测试接雨水
        System.out.println("=== 接雨水测试 ===");
        int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
        int result4 = trap(height);
        System.out.println("输入高度：" + Arrays.toString(height));
        System.out.println("接水量：" + result4);
    }
}